/// 滑动窗口问题


/// https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envType=study-plan-v2&envId=top-100-liked
/// 3. 无重复字符的最长子串
// 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串的长度。
// TIP: 滑动窗口一般可以通过确定的递推，迭代获取所有的情况
pub fn length_of_longest_substring(s: String) -> i32 {
    let mut max_len = 0;
    if s.is_empty() { return max_len; }
    let mut l = 0;
    let mut exist_char_map = std::collections::HashMap::new();
    for (i, v) in s.chars().enumerate() {
        if exist_char_map.contains_key(&v) {
            let last = exist_char_map[&v];
            exist_char_map.entry(v).and_modify(|e| *e = i);
            l = std::cmp::max(l, last + 1);
        }
        exist_char_map.insert(v, i);
        max_len = std::cmp::max(max_len, i as i32 - l as i32 + 1);
    }

    max_len
}

pub fn length_of_longest_substring2(s: String) -> i32 {
    use std::collections::HashSet;
    let mut res = 0;
    let mut record: HashSet<char> = HashSet::new();
    let mut r = 0;
    let cv = s.chars().collect::<Vec<char>>();
    // 贪心算法，从起始位置一直添加，直到出现重复
    for (i, v) in cv.iter().enumerate() {
        if i != 0 {
            // 移除上一个字符
            record.remove(&cv[i - 1]);
        }
        while r < cv.len() && !record.contains(&cv[r]) {
            record.insert(cv[r]);
            r += 1;
        }
        res = res.max(r - i);
        if r == cv.len() { break; }
    }
    res as i32
}


#[test]
pub fn test_length_of_longest_substring() {
    println!("{}", length_of_longest_substring2("abba".to_string()));
}


/// https://leetcode.cn/problems/find-all-anagrams-in-a-string/description/?envType=study-plan-v2&envId=top-100-liked
/// 438. 找到字符串中所有字母异位词
// 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
// TIP: 此类情况利用总字符的个数确定大小限制的数组保证对比的效率
pub fn find_anagrams(s: String, p: String) -> Vec<i32> {
    let mut record = vec![];
    if p.len() > s.len() { return record; }
    let mut pchars: Vec<char> = p.chars().collect();
    let mut pattern = vec![0; 26];
    for x in pchars {
        pattern[x as usize - 'a' as usize] += 1;
    }

    let mut matcher = vec![0; 26];
    let chars: Vec<char> = s.chars().collect();
    for &x in chars[0..p.len()].iter() {
        matcher[x as usize - 'a' as usize] += 1;
    }
    for i in 0..=chars.len() - p.len() {
        if matcher.eq(&pattern) {
            record.push(i as i32);
        }
        if i + p.len() < s.len() {
            matcher[chars[i + p.len()] as usize - 'a' as usize] += 1;
            matcher[chars[i] as usize - 'a' as usize] -= 1;
        }
    }
    record
}

#[test]
pub fn test_find_anagrams() {
    println!("{:?}", find_anagrams("cbaebabacd".to_string(), "abc".to_string()));
}